package com.lagou.demo02;

public class Homework2 {

    public static int[][] solution(int[] values,int[] persons, int max){
        //如果 values 为空或者 person 为空或者 max=0 直接 return
        if(values==null||values.length==0||persons==null||persons.length==0||values.length!=persons.length){
            return new int[0][0];
        }

        int[][] dp = new int[values.length+1][max+1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {
                if(persons[i-1]>j){//人数超出了允许人数
                    dp[i][j]=dp[i-1][j];
                }else {
                    //可以选择的情况
                    int preV = dp[i-1][j];//不选择
                    int curV = dp[i-1][j-persons[i-1]]+values[i-1];//选择
                    dp[i][j]=Math.max(preV, curV);
                }
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        int[] values={500,300,200,100,80};
        int[] persons={5,4,3,2,1};
        int max=10;
        int[][] solution = solution(values, persons, max);
        for (int i = 1; i < solution.length; i++) {
            if(solution[i][max]!=solution[i-1][max]){
                System.out.println("选择了:"+values[i-1]);
            }
        }


    }
}
